package leetcode_121_140;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

public class wordBreak_140 {
    /**
     * 在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。
     * 注意：词典中的同一个单词可能在分段中被重复使用多次。
     * @param s
     * @param wordDict 字符串字典
     * @return 以任意顺序 返回所有这些可能的句子
     */
    public List<String> wordBreak(String s, List<String> wordDict) {
        /**
         *1ms，还是按上一题的方法
         */
        int len=s.length();
        HashMap<Integer,List<StringBuilder>> map=new HashMap<>();  //k为单词长度，value为该长度的所有单词
        for (String word : wordDict) {
            int wordLen=word.length();
            if ( wordLen<= len) {  //长度不大于s的长度
                //添加到相同长度单词的集合中
                if(map.containsKey(wordLen)){
                    map.get(wordLen).add(new StringBuilder(word));
                }else {
                    List<StringBuilder>words=new ArrayList<>();
                    words.add(new StringBuilder(word));
                    map.put(wordLen,words);
                }
            }
        }
        boolean[] momo=new boolean[s.length()];         //是否无法继续拼接
        function(map,s.length(),new StringBuilder(),s,momo);
        return ans;
    }

    List<String> ans=new ArrayList<>();

    List<StringBuilder>words=new ArrayList<>(); //实时语句

    boolean function(HashMap<Integer,List<StringBuilder>>map,int len,StringBuilder Sb,String s,boolean[] momo){
         if(len==0){
            StringBuilder stringBuilder=new StringBuilder();
            for(int i=0;i<words.size();i++)
                stringBuilder.append(words.get(i)).append(" ");
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
            ans.add(stringBuilder.toString());
            return true;
        }
        if(momo[Sb.length()]==true) //此处之后无法组合单词拼接成功，直接跳过
            return false;

        boolean Flag=false;  //是否可以在这拼接

        for(int i=len;i>0;i--){  //优先拼接长单词
            if(map.containsKey(i)){
                for(StringBuilder sb:map.get(i)){
                    boolean flag=true; //该单词是否可以拼接
                    for (int t = 0; t < sb.length(); t++) {     //判断该单词是否可以拼接到对应位置
                        if (sb.charAt(t) != s.charAt(s.length() - len + t)) {
                            flag=false;
                            break;
                        }
                    }
                    if(flag){
                        words.add(sb);
                        if(function(map, len - sb.length(), new StringBuilder(Sb).append(sb),s,momo))
                            Flag=true;
                        words.remove(words.size()-1);
                    }
                }
            }
        }
        if (!Flag) {  //此处之后无法组合单词拼接成功,记录下来
            momo[Sb.length()] = true;
            return false;
        } else
            return true;
    }
}
